'''
Created on Dec 8, 2009

@author: pntruongan
'''
import sys

class BTNode:
    def __init__(self):
        self.item = None
        self.Left = None
        self.Right = None
    
    def __init__(self,item, left, right):
        self.item = item
        self.Left = left
        self.Right = right

class priorityQueue:
    def __init__(self):
        self.__List = []
    def push(self, node):
        i = 0
        #do a linear search for the appropriate spot for items
        while i < len(self.__List) and self.__List[i].item[1] < node.item[1]:
            i += 1
            
        self.__List.insert(i, node)
        
    def top(self):
        return self.__List[0]
    
    def count(self):
        return len(self.__List)
    
    def pop(self):
        '''
        Return top then remove top as well
        '''
        a = self.__List[0]
        self.__List = self.__List[1:len(self.__List)]
        return a


class bitWriter:
    def __init__(self, fileObj):
        '''
        fileobj a file that was already opened for writing
        '''
        
        if isinstance(fileObj, file) and fileObj.mode[0] == 'w':
            self._file = fileObj
            self._currentByte = 0
            self._curByteIdx = 0
        else:
            raise Exception
        
    def write(self, string):
        '''
        string is a sequence of '0' and '1' only.
        Any strange character is an exception
        '''
        for i in string:
            if (i != "0" and i !="1"):
                raise Exception
            
            b = int(i) #B is either 0000000 or 0000001
            b = b << (7 - self._curByteIdx) #move the last bit to desire position
            self._currentByte = self._currentByte | b #this will modify our desire bit in the current byte
            self._curByteIdx += 1
            
            if (self._curByteIdx == 8):
                #If our byte is full, write it down
                self._file.write( chr(self._currentByte) )
                self._curByteIdx = 0
                self._currentByte = 0    
    
    def end(self, close):
        '''
        close is a boolean. Set it to true if you want to close the file
        '''
        if (self._currentByte != 0):
            self._file.write( chr(self._currentByte))
        #self._file.flush()
        if close == True:
            self._file.close()

class bitReader:
    def __init__(self, fileObj):
        '''
        fileObj: a file that was already open
        '''
        if isinstance(fileObj, file):
            self._file = fileObj
            self._currentByte = 0
            self._curByteIdx = 0
        else:
            raise Exception
        
    def read(self):
        '''
        Return one bit. If EOF is reached, return None
        '''
        if self._currentByte == None:
            #If we ran out of bits in the current byte, read a new byte.
            a = self._file.read(1)
            if a == None:
                return None
            self._currentByte = ord(a) 
            self._curByteIdx = 0
        
        b = self._currentByte
        b = b >> (7 - self._curByteIdx) #move the desire bit to the end of the byte
        b = b & 1 #This will convert all previous bit to zero
        
        self._curByteIdx +=1
        if self._curByteIdx == 8:
            self._currentByte = None
        
        return str(b)
    
    def close(self):
        '''
        close the file
        '''
        self._file.close()
